const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
// 给定一个链表的头节点head，判断链表是否有环

// 思路1，哈希表思路
// 遍历所有节点，每个节点都用set判断是否访问过，如果访问过，说明有环，否则加入set中
function hasCycle(head) {
    let set = new Set()
    while (head) {
        if (set.has(head)) {
            return true
        } else {
            set.add(head)
            head = head.next
        }
    }
    return false
}

let list = new LinkedList([2, 5, 1, 7, 3, 9, 1])
let node1 = new ListNode(2)
let node2 = new ListNode(5)
let node3 = new ListNode(1)
let node4 = new ListNode(7)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

// console.log(hasCycle(list.head));
// console.log(hasCycle(node1));

// 思路2，快慢指针
// 快慢指针，slow和fast，slow每次走一步，fast每次走两步，两个指针在链表头节点外的某个节点相遇，说明链表有环
function hasCycle2(head) {
    if (!head || !head.next) {
        return false
    }
    let slow = head.next
    let fast = head.next.next
    while (slow !== fast) {
        if (!fast || !fast.next) {
            return false
        }
        slow = slow.next
        fast = fast.next.next
    }
    return true
}
console.log(hasCycle2(list.head));
console.log(hasCycle2(node1));